The present invention relates to an address translation and generation system. More particularly, the present invention relates to an improved address translation and generation system which does not require an associative memory.
In a multiprogrammed system, allocation of the main memory unit is generally performed before initiating execution of a program. In the course of executing the program, dynamic relocating must sometimes be performed to relocate information stored in the main memory unit. Thus, there is no way of knowing, during programming and translating procedures, from which location of the main memory unit the program in question will be executed. For this reason, it is impossible to specify by program a particular address in the main memory unit during programming or compiling. The addresses used in programming must be allocated independently of addresses of the main memory unit. Such an address used in programming is called a logical address, and an address allocated in the main memory unit is called a physical address.
In general, the logical addresses of a program consist of consecutive addresses starting from 0. The area specified by the consecutive addresses starting from 0 is called the address space of the program. Each address thus has its own program space consisting of logical addresses which are only effective in that program. In a multiprogrammed system, a plurality of programs each having its own address space are stored in the main memory unit, and are executed simultaneously. The multiprogrammed system requires hardware for automatically converting logical addresses of the program into physical addresses. In an information processing system which adopts an addressing system which automatically converts logical addresses into physical addresses, it has been the general practice to convert a logical address into a physical address for memory access by referring to an address conversion table in the main memory unit every time an instruction is executed. When this addressing system is adopted, the address conversion table in the main memory unit must be referred to many times, resulting in a decrease in the efficiency of program execution.
An improved addressing system over such a prior art system has been proposed according to which the entries of the address conversion table which are most frequently used are stored in a high speed associative memory so as to reduce the frequency of memory access. However, with this address converting system, the address conversion table in the main memory must also be referred to in the case of entries which are not stored in the associative memory, and execution efficiency is thereby degraded. Furthermore, for effective use of the associative memory, its capacity must be increased or an efficient mechanism for storing and retrieving the contents must be adopted, increasing the cost of a medium or small scale computer and reducing its cost competitiveness. In addition to this, in the use of a so-called "virtual memory" with a conventional dynamic address converting system, when the data or an instruction required is not found in the main memory unit during execution of the instruction, execution of the instruction must be interrupted. Then, the required data or the instruction must be read into the main memory unit from an external memory unit, and thereafter the interrupted instruction may be restarted. For restarting general computer instructions which require special operations for roll-in and roll-out, after interruption of such an instruction, restarting of the interrupted instruction requires highly advanced techniques and costly systems which are imcompatible with the requirements of medium and small scale computers. For example, a technique is required for determining whether or not the data or another instruction necessary for execution of an instruction are in the main memory unit before execution of the instruction, and a technique is required which reserves or restores a number of registers within hardware for execution of the instruction.
Larger main memory units are being used as memory is becoming less expensive, and the number of physical addresses involved is correspondingly increasing. The problem of addressing the larger memory units may not be completely solved by expanding the address specifying unit for the instructions. It is considered essential to develop software based on logical addresses and to adopt a system for converting logical addresses into physical addresses. However, with the dynamic address converting system adopted in a prior art computer, logical addresses are converted into physical addresses during execution of each of the instructions. The efficient use of this system requires an expensive device such as an associative memory, and this system is not suitable for medium or small scale computers.